In many prior vehicle location and vehicle navigation systems, an estimated position of a vehicle is first determined and then compared with positions of fixed roadways which are defined by road map data stored in a memory. A position/navigation computer then first determines what roadways are close to the estimated position of the vehicle. Then the computer corrects the position of the vehicle by map matching techniques in which the vehicle position is located on the most probable one of the roadways previously identified as being close to the estimated position of the vehicle. Many prior systems utilize such map matching techniques wherein the history of prior vehicle travel, as well as the current estimated position of the vehicle, its prior sensed heading and its current sensed heading are used to accomplish map matching. Since it is assumed that the vehicle is on a fixed roadway and since accurate coordinates of fixed roadways are stored in a memory, a more accurate corrected position of the vehicle is achieved. Then the prior systems utilize this corrected vehicle position information as the current vehicle position and information is provided to the vehicle driver.
Based on the corrected position, the prior systems either calculate desired navigation routes to a desired destination and provide route information to a user, or they provide updated position information to a user and/or to a navigation computer which provides user navigation information based on the current corrected position. Typically, information is provided to the user by means of a visual display, which may or may not be supplemented by audible signals. This information could include navigation turning instructions for following a planned route.
A first step in providing for map matching is the identification of what stored road segments are close to the initial estimated position of the vehicle. This simplifies the map matching techniques because it limits the number of road segments which will be investigated as possible locations for the vehicle. Typically the road segments are stored in memory by virtue of their start and end Cartesian coordinates. One prior system apparently identified which road segments were close to the estimated vehicle position by defining an area (subregion) around the estimated position. Then this prior system created a list of road segments which had at least a portion inside the subregion. The prior system apparently solved simultaneous equations which define the road segment and the boundaries of the area around the estimated vehicle position. If a solution existed, then the road segment was known to intersect the area boundaries and the road segment was identified as close. A computer can relatively quickly solve such equations to therefore determine if a road segment is close to the estimated vehicle position. However, when a very large number of road segments must be investigated, this process becomes very time consuming.
In the field of computer graphics line clipping, the problem of displaying only the portions of line segments which are inside a "window" is solved. This problem is generally solved by the use of coordinate comparison signals which are then analyzed to eliminate some line segments from consideration before resorting to equation solving. However, the standard computer graphics line clipping techniques, even if they were applied to the present problem, still require equation solving for a large number of possible road segments. Thus, there is a need for an improved apparatus which more efficiently determines which road segments are close to an initial estimated vehicle position.